package com.zwx.aray.sigLianBiao;

/**
 * 单链表排序算法实现
 *
 * @author 文希
 * @create 2019-06-01 22:01
 */
public class Test01 {
    public static void main(String[] args) {

    }

    /**
     * 单链表排序与数组排序思路是一样的，只是两个游标的移动方式不同。
     *
     * 单链表排序的两个游标向同一方向移动，p、q代指两个游标，p左侧的都是比驱轴小的，p到q是比轴大的，
     * q右侧的是还未排序的。
     *
     *
     */
    private static void quickSort(Node head,Node tail){
        if (head != tail && head.getNext() != tail){
            // 至少有两个元素才排序
            Node privot = partition(head,tail);
            quickSort(head,privot);
            quickSort(privot.getNext(),tail);
        }
    }

    private static Node partition(Node head, Node tail) {

        Node cur = head.getNext(); // 游标 q
        Node mid = head.getNext(); // 游标 p
        Node midPrev = head;
        Node pivot = null;
        int pivotVal = head.getVal();

        do {
            while (mid.getNext() != tail && mid.getVal() <= pivotVal) {
                // 找到下一个比枢轴大的元素
                midPrev = mid;
                mid = mid.getNext();
            }
            if (cur == head.getNext()) {
                // q 游标第一次移动前的初始化，保证 q 在 p 右侧
                cur = mid;
            }
            while (cur.getNext() != tail && cur.getVal() > pivotVal) {
                // 找到下一个比枢轴小的元素
                cur = cur.getNext();
            }
            if (cur.getNext() != tail && mid.getNext() != tail) {
                // 如果两个游标都未到结尾
                swap(cur, mid);
            } else {
                if (cur.getNext() == tail && cur.getVal() < pivotVal) {
                    // 如果 q 游标到结尾了并且该节点的值小于枢轴
                    swap(mid, cur);
                }

                // 将枢轴交换到中间，保证左侧都小于枢轴，右侧都大于枢轴
                if (mid.getVal() < pivotVal) {
                    swap(mid, head);
                    pivot = mid;
                } else {
                    swap(midPrev, head);
                    pivot = midPrev;
                }
            }
            cur = cur.getNext();
            midPrev = mid;
            mid = mid.getNext();
        } while (cur != tail && mid != tail);

        return pivot;
    }

   private static void swap(Node node1, Node node2) {
        int temp = node1.getVal();
        node1.setVal(node2.getVal());
        node2.setVal(temp);
    }
}
